// https://leetcode.cn/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 遍历区间列表，分三个阶段处理新区间插入
// 2. 第一阶段：添加所有结束位置小于新区间开始的区间
// 3. 第二阶段：合并所有与新区间重叠的区间，更新边界
// 4. 第三阶段：添加剩余的不重叠区间
// 5. 时间复杂度：O(N)，空间复杂度：O(1)（不计返回结果）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) 
    {
        int m = intervals.size();
        vector<vector<int>> ret;

        int i = 0, l = newInterval[0], r = newInterval[1];
        while (i < m && intervals[i][1] < l)
        {
            ret.push_back({intervals[i][0], intervals[i][1]});
            i++;
        }

        while (i < m && intervals[i][0] <= r)
        {
            l = min(l, intervals[i][0]);
            r = max(r, intervals[i][1]);
            i++;
        }
        ret.push_back({l, r});

        while (i < m)
        {
            ret.push_back({intervals[i][0], intervals[i][1]});
            i++;
        }

        return ret;
    }
};

int main()
{
    vector<vector<int>> intervals1 = {{1,3},{6,9}};
    vector<vector<int>> intervals2 = {{1,2},{3,5},{6,7},{8,10},{12,16}};
    vector<int> newInterval1 = {2,5};
    vector<int> newInterval2 = {4,8};

    Solution sol;

    auto vv1 = sol.insert(intervals1, newInterval1);
    auto vv2 = sol.insert(intervals2, newInterval2);

    for (const auto& v : vv1)
    {
        for (const int& num : v)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    cout << endl;

    for (const auto& v : vv2)
    {
        for (const int& num : v)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}